package 链表;

import java.util.List;

/**
 *https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
 */
public class _19_删除链表的倒数第N个结点 {
     public class ListNode {
       int val;
       ListNode next;
       ListNode() {}
       ListNode(int val) { this.val = val; }
       ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     }

     //双指针法
     public ListNode removeNthFromEnd2(ListNode head, int n) {
         if(head == null) return null;

         ListNode fast = head;
         ListNode slow = head;

         //快指针先走n步
         for(int i=0;i<n;++i){
             fast = fast.next;
         }

         //需要找到待删除的上一个节点，所以快指针和慢指针只需要在走一遍n步，慢指针此时就指向被删除的上一个
         while(fast.next!=null){
             fast = fast.next;
             slow = slow.next;
         }
         slow.next = slow.next.next;

         return head;
     }


    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head == null) return null;
        ListNode p = head;
        int size = size(p);
        //特殊情况
        if(size == n) return head.next;

        //走到倒数第n个节点的前一个
        for(int i=0;i<size-n-1;++i){
            p = p.next;
        }
        ListNode remove = p.next;
        p.next = remove.next;
        return head;
    }

    //计算链表节点的个数
    private int size(ListNode head){
        ListNode tmp = head;
        int size =0;
        while(tmp!=null){
            size++;
            tmp = tmp.next;
        }
        return size;
    }
}
